import java.util.*;

public class ParsingTable
{
	/*Notation:
	 * head: nonterminal that a given rule substitutes (ex: A -> BC, A is the head)
	 * first: member of the firsts set
	 * tail: the substitution for the head of a rule
	 * token: members of a rule's "tail"
	 */
	private Map<String, Map<String, Rule>> parseTable;	//maps heads to "first"s to rules
	private Set<String> allTokens;						//convenient way to store all the possible tokens
	
	private ParsingTable()
	{
		parseTable = new HashMap<String, Map<String, Rule>>();
		allTokens = new HashSet<String>();
	}
	
	public ParsingTable(ArrayList start, ArrayList terminals, ArrayList nonterminals, Rule[] rules)
	{
		//initialize data structs
		this();
		
		/*Set Firsts for terminals*/
		for(Rule rule : rules)
		{
			String token = rule.tail.split(" ")[0];
			if(terminals.contains(token) || token.equals("E"))
			{
				rule.first = token;
				AddRule(rule);
			}
		}
		
		/*Calculate Firsts for nonterminals*/
		CalculateFirsts(terminals, nonterminals, rules);
	}
	
	/*Calculate Firsts Set, Add to ParseTable*/
	private void CalculateFirsts(ArrayList terminals, ArrayList nonterminals, Rule[] rules)
	{
		boolean changes;
		do
		{
			changes = false;
			
			/*foreach rule*/
			for(Rule production : rules)
			{
				/*use only rules that substitute nonterminals*/
				if(!terminals.contains(production.head))
				{
					int k = 0;
					boolean cont = true;
					
					/*symbols - individual symbols in this substitution rule*/
					String[] symbols = production.tail.split(" ");
					
					/*Cycle thru all such symbols*/
					while(cont && k <= symbols.length)
					{
						cont = false;
						
						/*token - the current symbol of this substitution rule*/
						String token = symbols[k];
						
						/*token is only helpful if it's already been evaluated 
						 * and placed in the parse table*/
						if(parseTable.containsKey(token))
						{
							/*Cycle thru token's firsts*/
							for(String first : parseTable.get(token).keySet())
							{
								/*if token is nullable, continue our search!*/
								if(first.equals("E"))
								{
									cont = true;
									k++;
								}
								/*add any of token's non-E firsts to this rule's head*/
								else
								{
									if(parseTable.get(production.head) == null || 
										!production.equals(parseTable.get(production.head).get(production.first)))
									{
										changes = true;
									}
									
									production.first = first;
									AddRule(production);
									cont = false;
								}
							}
						}
					}
					/*cont will only be true if all symbols that can substitute this rule's head are nullable, 
					 * therefore production's head is nullable*/
					if(cont)
					{
						/*This is especially important when ScannerII
						 * Essentially performs the duty of the follow set
						 * by replacing strings with E if they are nullable and no other rule matches*/
						production.first = "E";
						AddRule(production);
					}
				}
			}
		}while(changes);
	}
	
	/*Adds a rule to the parsing table at [rule.head, rule.first]*/
	private void AddRule(Rule rule)
	{
		if(parseTable.containsKey(rule.head))
		{
			parseTable.get(rule.head).put(rule.first, rule);
		}
		else
		{
			parseTable.put(rule.head, new HashMap<String, Rule>());
			parseTable.get(rule.head).put(rule.first, rule);
		}
		
		allTokens.add(rule.first);
	}
	
	/*Checks to see if there is a substitution for the head nonterminal given first*/
	public boolean HasRule(String head, String first)
	{
		return (parseTable.containsKey(head) && parseTable.get(head).containsKey(first));
	}
	
	/*Returns the rule for the head nonterminal given first or null if that rule does not exist*/
	public Rule getRule(String head, String first)
	{
		if(HasRule(head,first))
		{
			return parseTable.get(head).get(first);
		}
		
		return null;
	}
	
	/*Prints the table in human-readable form*/
	public void PrintTable()
	{
		for(String head : parseTable.keySet())
		{
			System.out.println(head+" - ");
			
			for(String first : allTokens)
			{
				System.out.print("\t\""+first+"\": ");
				if(HasRule(head, first))
				{
					System.out.println(parseTable.get(head).get(first).tail);
				}
				else
				{
					System.out.println("NULL ");
				}
			}
			
			System.out.println();
		}
	}
	
	/*Prints the table in CSV form*/
	public void PrintCSV()
	{
		System.out.print(",");
		for(String token : allTokens)
		{
			System.out.print(token+",");
		}
		
		System.out.println();
		
		for(String head : parseTable.keySet())
		{
			System.out.print(head+",");
			for(String token : allTokens)
			{
				if(HasRule(head, token))
				{
					System.out.print(parseTable.get(head).get(token).tail+",");
				}
				else
				{
					System.out.print(",");
				}
			}
			System.out.println();
		}
	}
}
